package 堆;

import java.util.PriorityQueue;

/*原始堆排序*/
public class HeapSort {
    private HeapSort(){};
    public static <E extends Comparable<E>> void sort(E []arr){
        MaxHeap<E> maxHeap = new MaxHeap<>(10);
        for (E n: arr){
            maxHeap.add(n);
        }
        for (int i = arr.length - 1; i >= 0; i--) {
            arr[i] = maxHeap.deleteMax();
        }
    }
    public static <E extends Comparable<E>> void sort1(E [] arr){
        if (arr.length <= 1) return;
        for(int i = (arr.length - 2)/2; i>= 0; i--){
            shiftDown(arr, i, arr.length);
        }
        for (int i = arr.length - 1; i >= 0 ; i--) {
            swap(arr, 0, i);
            shiftDown(arr, 0, i);
        }
    }
//    data[0,n) 的最大堆中, 索引k的元素执行
    private static<E extends Comparable<E>>
    void shiftDown(E [] data, int index, int n) {
        while (2 * index + 1 < n){
            int j = 2 * index + 1;
            if((j+1) < n &&
                    data[j+1].compareTo(data[j]) > 0){
                j++;
            }
            if (data[index].compareTo(data[j]) > 0){
                break;
            }
            swap(data, j, index);
            index = j;
        }
    }
    public static <E>
    void swap(E[]data, int i, int j){
        E temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }

    public static void main(String[] args) {
//        Integer []arr = {5,4,6,2,1,8};
//        sort1(arr);
//        for (Integer n :
//                arr) {
//            System.out.print(n+" ");
//        }
//        PriorityQueue<Object> priorityQueue = new PriorityQueue<>();
        System.out.println('s'+10);
    }
}
